package com.ywk.base.dataStructure.stack;
//双链表实现栈（后进先出）
public class LinkedListStackDemo {

	public static void main(String[] args) {
		StackNode sn1=new StackNode(10);
		StackNode sn2=new StackNode(20);
		StackNode sn3=new StackNode(30);
		LinkedListStack ls=new LinkedListStack();
		ls.push(sn1);
		ls.push(sn2);
		ls.push(sn3);
		ls.showStack();
		System.out.println(ls.pop());
	}

}


class LinkedListStack{
	private StackNode head=new StackNode();
	private StackNode top;//栈顶指针,指向链表最后的结点
	
	//入栈，每次入栈的节点添加到最后，然后将栈顶指针指向这个新添加的结点
	public void push(StackNode sn) {
		if(head.next==null) {
			top=head;
		}
		top.next=sn;
		sn.pre=top;
		top=top.next;
	}
	//出栈，每次出栈的节点都是栈顶的结点
	public StackNode pop() {
		StackNode sn=top;
		top=top.pre;
		return sn;
	}
	
	public void showStack() {
		StackNode p=head.next;
		if(p==null) {
			System.out.println("栈空");
			return;
		}
		while(true) {
			System.out.println(p);
			if(p.next==null) {
				break;
			}
			p=p.next;
		}
	}
}


class StackNode{
	private int value;
	public StackNode next;
	public StackNode pre;
	
	public StackNode() {}
	
	public StackNode(int value) {
		super();
		this.value = value;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	@Override
	public String toString() {
		return "StackNode [value=" + value + "]";
	}
}